package com.kristin.sort;

/**
 * 插入排序
 * 已排序和未排序的序列，将未排序的序列，在已排序的序列中找到一个合适的位置进行插入
 */
public class InsertSort {

    public void sort(int[] arrs) {
        for(int i = 1 ; i < arrs.length ; i++) {
            int current = arrs[i];
            int preIndex = i - 1;

            while(preIndex >=0 && arrs[preIndex] > current) {
                arrs[preIndex + 1] = arrs[preIndex];
                preIndex --;
            }
            arrs[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] arrs = new int[]{10, 9, 8, 7, 4, 3, 2, 1, 6, 5};
        new InsertSort().sort(arrs);
        print(arrs);
    }

    public static void print(int[] arrs) {
        for (int i : arrs) {
            System.out.print(i + "\t");
        }
    }

}
